package com.ma.graph;

import com.ma.graph.mst.UF;

/**
 * 给你输入编号从0到n - 1的n个结点，和一个无向边列表edges（每条边用节点二元组表示），请你判断输入的这些边组成的结构是否是一棵树。
 * n = 5
 * edges = [[0,1], [0,2], [0,3], [1,4]]
 */
public class Solution261 {
    public static boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            if (uf.connected(u, v)) {
                return false;
            }
            uf.union(u, v);
        }
        return uf.getCount() == 1;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
        System.out.println(validTree(n, edges));

        int n1 = 5;
        int[][] edges1 = {{0,1},{1,2},{2,3},{1,3},{1,4}};
        System.out.println(validTree(n1,edges1));

    }

}
